public class Solution300 {
    public int lengthOfLIS(int[] nums) {
        int[] f=new int[nums.length+1];
        int len=0;
        f[0]=Integer.MIN_VALUE;
        for (int num : nums) {
            if (num>f[len]){
                len++;
                f[len]=num;
            }else{
                int l=0,r=len-1,ans=-1;
                while (l<=r){
                    int mid=(l+r)/2;
                    if (num<=f[mid]){
                        r=mid-1;
                    }else if (num>f[mid+1]){
                        l=mid+1;
                    }else{
                        ans=mid;
                        break;
                    }
                }
                f[ans+1]=num;
            }
        }
        return len;
    }

    public static void main(String[] args) {
        System.out.println(new Solution300().lengthOfLIS(new int[]{10,9,2,5,3,7,101,18}));
    }
}
